package com.huawei.ispace.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
    public class DFA {   
        String content2 = "规划纲要还提出，推进事业单位养老保险制度改革。研究制定公务员和参照公务员法管理单位的工作人员养老保险办法。" +
		"目前我国事业单位养老保险改革试点已经启动，2008年国务院出台了事业单位养老保险制度试点改革方案，确定在山西、上海、浙江、广东和重庆5省市先期试点改革。改革的主要内容就是事业单位养老保险制度与城镇职工养老保险制度看齐。" +
		"记者了解到，人社部年初已专门发文，将推动事业单位养老保险改革。这项改革也列入了今年我国深化经济体制改革的重点工作。";   
        
        private String[] arr2 = {"要还", "国务院", "养老保", "国务院", "改革", "深化", "解到"};   
        
        private String[] arr = arr2;// {"DFA", "恶心", "DA"};
       
        private Node rootNode = new Node('R');   
               
        private String content = content2;// "Hello DFA World DFA, HaHa! 恶心";
        
      //  private List<String> words = new ArrayList<String>();      
      //  private List<String> word = new ArrayList<String>();   
        int a = 0;   
        private StringBuilder strWord = new StringBuilder();
           
        private void searchWord() {   
            char[] chars = content.toCharArray();   
            Node node = rootNode;   
            while(a<chars.length) {   
                node = findNode(node,chars[a]);   
                if(node == null){
                	node = rootNode;   
                	strWord.append(chars[a]);
                }else{
                	strWord.append("*");
                }
               /* if(node == null) {   
                    node = rootNode;   
                    a = a - word.size();   
                    word.clear();   
                } else if(node.flag == 1) {   
                    word.add(String.valueOf(chars[a]));   
                    StringBuffer sb = new StringBuffer();   
                    for(String str : word) {   
                        sb.append(str);   
                    }   
                    words.add(sb.toString());   
                    a = a - word.size() + 1;   
                    word.clear();   
                    node = rootNode;   
                } else {   
                    word.add(String.valueOf(chars[a]));   
                }   */
                a++;   
             
            }   
            //System.out.println(strWord);
        }   
           
        private void createTree() {   
            for(String str : arr) {   
                char[] chars = str.toCharArray();   
                if(chars.length > 0)   
                    insertNode(rootNode, chars, 0);   
            }   
        }   
           
        private void insertNode(Node node, char[] cs, int index) {   
            Node n = findNode(node, cs[index]);   
            if(n == null) {   
                n = new Node(cs[index]);   
                node.nodes.add(n);   
            }   
               
            if(index == (cs.length-1))   
                n.flag = 1;   
                   
            index++;   
            if(index<cs.length)   
                insertNode(n, cs, index);   
        }   
           
        private Node findNode(Node node, char c) {   
            List<Node> nodes = node.nodes;   
            Node rn = null;   
            for(Node n : nodes) {   
                if(n.c==c) {   
                    rn = n;   
                    break;   
                }   
            }   
            return rn;   
        }   
        
        
        public void test(){
        	String content = content2;//"Hello DFA World DFA, HaHa! 恶心";
        	String[] arr = arr2;//{"DFA", "恶心", "DA"};  
        	char contents[] = content.toCharArray();
        	Map<Character, List<String>> word = new HashMap<Character, List<String>>();
        	for(String str : arr){
        		char key = str.charAt(0);
        		List<String> list = word.get(key);
        		if(list == null){
        			list = new ArrayList<String>();
        			list.add(str);
        			word.put(key, list);
        		}else{
        			list.add(str);
        		}
        	}

        	for(int i = 0 ; i < contents.length; i++){
        		List<String> list = word.get(contents[i]);
        		
        		if(list == null){
        			continue;
        		}
        		
        		for(String str : list){
        			char words[] = str.toCharArray();
        			boolean mark = true;
    				for(int j = 0; j < words.length; j++){
    					if(words[j] != contents[j+i]){
    						mark = false;
    						break;
    					}
    				}
    				
    				if(mark){
    					for(int j = 0; j < words.length; j++){
    						contents[i++] = '*';
    					}
    				}
    			}
        	}
        	
        	//System.out.println(new String(contents));

        }
           
        public static void main(String[] args) {   
        	long start = System.currentTimeMillis();
            for(int i = 0; i < 10000 ; i++){
            	 DFA dfa = new DFA(); 
            	 dfa.createTree();   
                 dfa.searchWord();   
            	 //dfa.test();
            }
            long end =System.currentTimeMillis();
            
            System.out.println(end - start);
          /*  dfa.createTree();   
            dfa.searchWord();   
            System.out.println(dfa.words);   
            System.out.println(dfa.strWord);*/
        }   
           
           
        private static class Node {   
            public char c;   
            public int flag; //1：表示终结，0：延续   
            public List<Node> nodes = new ArrayList<Node>();   
               
            public Node(char c) {   
                this.c = c;   
                this.flag = 0;   
            }   
               
            public Node(char c, int flag) {   
                this.c = c;   
                this.flag = flag;   
            }   
        }   
    } 

